#include <iostream>
#include <vector>
using namespace std;

/*
我们都知道安卓有个手势解锁的界面，是一个 3 x 3 的点所绘制出来的网格。用户可以设置一个 “解锁模式” ，通过连接特定序列中的点，形成一系列彼此连接的线段，每个线段的端点都是序列中两个连续的点。如果满足以下两个条件，则 k 点序列是有效的解锁模式：
点位按行优先排列1~9
解锁模式中的所有点 互不相同 。
假如模式中两个连续点的线段需要经过其他点，那么要经过的点必须事先出现在序列中（已经经过），不能跨过任何还未被经过的点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/android-unlock-patterns
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

class Solution
{
public:
    int numberOfPatterns(int m, int n)
    {
        int ans = 0;
        for (auto cur : {1, 2, 5})
        {
            int tmp = 0;
            vector<bool> visit(10, false);
            visit[cur] = true;
            backtrace(tmp, visit, cur, m - 1, n - 1);
            ans += cur == 5 ? tmp : 4 * tmp;
        }
        return ans;
    }

    void backtrace(int &ans, vector<bool> &visit, int last, int m, int n)
    {
        if (m <= 0)
            ans++;
        if (n == 0)
            return;
        for (int cur = 1; cur <= 9; ++cur)
        {
            if (valid(last, cur, visit))
            {
                visit[cur] = true;
                backtrace(ans, visit, cur, m - 1, n - 1);
                visit[cur] = false;
            }
        }
    }

    bool valid(int last, int cur, vector<bool> &visit)
    {
        if (visit[cur])
            return false;
        if (last == 5 || cur == 5)
            return true;
        if (last % 2 == 0)
        {
            if (cur % 2 == 1)
                return true;
            if (last == 2 || last == 8)
                return cur == 4 || cur == 6 || visit[5];
            if (last == 4 || last == 6)
                return cur == 2 || cur == 8 || visit[5];
        }
        if (last % 2 == 1)
        {
            if (cur % 2 == 0)
                return true;
            return visit[(last + cur) / 2];
        }
        return false;
    }
};